#include <stdio.h>

// 打印数组元素的函数
void print_arr(int *p, int len){
    for(int i = 0; i < len; i++){
        printf("%d  ", p[i]);
    }
    printf("\n");
}

// 一趟排序的函数
int one_sort(int *p, int low, int high){
    int flag = p[low];
    while(low < high){
        while(p[high] > flag && low < high){ // 如果是降序 将此处的 p[high] > flag 改成 p[high] < flag
            high--;
        }
        if(low < high){
            p[low] = p[high];
            low++;
        }
        while(p[low] < flag && low < high){ // 如果是降序 将此处的 p[low] < flag 改成 p[low] > flag
            low++;
        }
        if(low < high){
            p[high] = p[low];
            high--;
        }
    }
    // 记得把 flag 塞回去
    p[low] = flag; // 这里写 p[high] = flag 也可以 因为此时 low==high
    return low; // 这里写 return high 也可以 因为此时 low==high
}

// 快速排序的函数
int quick_sort(int *p, int low, int high){
    if(low < high){
        int ret = one_sort(p, low, high);
        quick_sort(p, low, ret-1);
        quick_sort(p, ret+1, high);
    }
}

int main(int argc, const char *argv[]){
    int s[10] = {6, 4, 1, 10, 5, 7, 2, 8, 3, 9};
    // 排序前
    print_arr(s, 10);

    // 快速排序
    quick_sort(s, 0, 9);

    // 排序后
    print_arr(s, 10);

    return 0;
}